package ch01;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Given two strings, write a method to decide if one is a permutation of the 
 * other.
 * @author Xi Chen
 *
 */

public class IsPermutation_03 {
	
	/**
	 * O(nlog(n))
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static boolean isPermutation(String s1, String s2) {
		if (s1.length() != s2.length()) {
			return false;
		}
		ArrayList<Character> list1 = new ArrayList<Character>();
		ArrayList<Character> list2 = new ArrayList<Character>();
		
		for (int i = 0; i < s1.length(); i++) { // O(n)
			list1.add(s1.charAt(i));
			list2.add(new Character(s2.charAt(i)));
		}
		Collections.sort(list1); // O(nlog(n))
		Collections.sort(list2);
		return (list1.equals(list2) ? true : false);
	}

	public static void main(String[] args) {
		String s1 = "a2abcbbdef";
		String s2 = "fabacedbb2";
		System.out.println(isPermutation(s1, s2));
	}

}
